package offer;

public class offerII_0094 {
    public int minCut(String s) {
        int len=s.length();
        if(len==1) return 0;
        char[] list=s.toCharArray();
        boolean[][] huiwen=new boolean[len][len];
        for(int i=0;i<len;++i){
            huiwen[i][i]=true;
        }
        for(int i=0;i<len-1;++i){
            huiwen[i][i+1]=(list[i]==list[i+1]);
        }
        for(int j=2;j<len;++j){
            for(int i=0;i+j<len;++i){
                huiwen[i][i+j]=(list[i]==list[i+j])&&huiwen[i+1][i+j-1];
            }
        }
        int[] dp=new int[len];
        for(int i=0;i<len;++i){
            dp[i]=Integer.MAX_VALUE;
        }
        dp[0]=0;
        if(list[0]==list[1]) dp[1]=0;
        else dp[1]=1;
        for(int i=2;i<len;++i){
            for(int j=0;j<=i;++j){
                if(huiwen[j][i]){
                    if(j==0){
                        dp[i]=0;
                    }
                    else {
                        dp[i]=Math.min(dp[i],dp[j-1]+1);
                    }
                }
            }
        }
        return dp[len-1];
    }
}
